/*
给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"
示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


执行用时 :4 ms, 在所有 C++ 提交中击败了86.13%的用户
内存消耗 :6.4 MB, 在所有 C++ 提交中击败了100.00%

复杂度分析：
逆序是O(n),循环里也是O(n),复杂度是O(n)

本来以为自己写了一堆垃圾，结果还不错，哈哈

中间部分解释一下，以免以后忘了

sum有四种情况：(顺序调换不会影响)
48(0)	48(0)	0		96		//此时cf = 0；ans[j] = 0;
49(1)	48(0)	0		97		//此时cf = 0；ans[j] = 1;
49(1)	48(0)	1		98		//此时cf = 1；ans[j] = 0;
49(1)	49(1)	1		99		//此时cf = 1；ans[j] = 1;
这是算法的核心
最后别忘了如果算出的结果是以零结尾，则需要把最后以为去除
如 0 和 0 相加 此时ans的大小为2，如果不去除最后一位就会变成00
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    string addBinary(string a, string b) {
        string a1 = a;
        string b1 = b;

        reverse(a1.begin(), a1.end());
        reverse(b1.begin(), b1.end());
        int cf = 0, size = a1.size() > b1.size() ? a1.size() + 1 : b1.size() + 1;
        unsigned int j = 0;
        string ans(size,'0');
        while (j < size) {
            char c1 = j < a1.size() ? a1[j]: '0';
            char c2 = j < b1.size() ? b1[j]: '0';
            int sum = c1 + c2 + cf;
            if (sum == 96) {
                cf = 0;
                ans[j] = '0';
            }
            else if (sum == 97) {
                cf = 0;
                ans[j] = '1';
            }
            else if (sum == 98) {
                cf = 1;
                ans[j] = '0';
            }
            else {
                cf = 1;
                ans [j] = '1';
            }
            j++;
        }
        if (ans[size - 1] == '0') {
            ans = ans.substr(0, ans.size() - 1);
        }
        reverse(ans.begin(), ans .end());
        return ans;
    }
};
int main(int argc, char const* argv[]) {
    Solution s;
    string a = "11001";
    string b = "111";
    cout << s.addBinary(a, b) << endl;

    return 0;
}
